package com.yinxin.wudasuanfa.sort;


import java.security.cert.TrustAnchor;
import java.util.Arrays;
import java.util.TreeMap;

/**
 * @author yinxin
 * @version 1.0
 * @Description: 快速排序 (分治思想)
 * @date 2022/4/1814:27
 */
public class QuickSort {

    public static void main(String[] args) {
//        int[] arr = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
        int[] arr = {4, 2, 1};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 分区过程
     * a[] 待分区数组
     * left 待分区数组最小下标
     * right 待分区数组最大下标
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int temp = qSort(arr, left, right);
            quickSort(arr, left, temp - 1);
            quickSort(arr, temp + 1, right);
        }
    }

    /**
     * 排序过程
     * arr 待排序数组
     * left 待排序数组最小下标
     * right 待排序数组最大下标
     *
     * @return 排好序之后基准数的位置下标，方便下次的分区
     */
    public static int qSort(int[] arr, int left, int right) {
        int temp = arr[left];//定义基准数，默认为数组的第一个元素
        while (left < right) {//遍历一边找一个最左边的值和一个最左边的值交换
            //在满足左边界小于右边界的情况下，从右边界开始找到arr中小于边界值的数
            while (left < right && arr[right] > temp) {
                right--;
            }
            //上面找出了基数右边从最右往基数往中间数的数中小于基数的索引，索引为right
            if (left < right) {
                arr[left++] = arr[right];
            }
            //在满足左边界小于右边界的情况下，从左边界开始找到arr中大于边界值的数
            while (left < right && arr[left] <= temp) {
                left++;
            }
            //上面找出了基数左边从最左往基数往中间数的数中大于基数的索引，索引为left
            if (left < right) {
                arr[right--] = arr[left];
            }
        }
        System.out.println(left== right);
        //当循环结束说明左指针和右指针已经相遇。并且相遇的位置是一个空出的位置，
        //这时候将基准数填入该位置，并返回该位置的下标，为分区做准备。
        arr[right] = temp;
        return right;
    }

}
